Computerized devices control almost every aspect of our life—from writing documents to controlling traffic lights. However, computerized systems are bug-prone, and thus require a testing phase in which the bugs should be discovered. The testing phase is considered one of the most difficult tasks in designing a computerized device. The cost of not discovering a bug may be enormous, as the consequences of the bug may be disastrous. For example, a bug may cause the injury of a person relying on the designated behavior of the computerized system. Additionally, a bug in hardware or firmware of a marketed product may be expensive to fix, as patching it requires call-back of the computerized device. Hence, many developers of computerized systems invest a substantial portion of the development cycle to discover erroneous behaviors of the computerized device.
An important part of testing relates to test planning and design, i.e., providing a set of tests that adequately cover the system, such that if all tests pass, the system is assumed to be operative. However, it is generally required to increase testing efficiency and reduce the number or total cost of the tests as much as possible.
A common methodology for test planning and design comprises the usage of combinatorial models, also referred to as Cartesian-product models, which may be used when describing a problem as a set of attributes or properties, values corresponding to the attributes, and possibly restrictions on combinations of values that may not appear together in a test. Each test comprises a value for each attribute, such that the combination represents a particular situation. Thus, a test may be represented as a tuple in which every attribute is assigned a value. The model thus spans a space of valid tests, being the value assignments that do not violate any restrictions.
Combinatorial models may be used as input to Combinatorial Test Design (CTD), a test planning technique that selects a subset of the valid test space which covers all interactions up to a certain level, which may be user-defined. Another important usage is for analysis of functional coverage of systems.
The CTD may thus output a test suite comprising a fraction of the test space that meets the coverage requirements. Coverage requirements may be given as a level of interaction, where, e.g., a “level 2” requirement stands for “for every pair of attributes, cover every possible pair of values”.
A test in this setting is a mere assignment of a value for each attribute. The order in which the attributes are set is often of significance, but is not handled by current approaches. For example, in a graphic user interface in which a user has to select a state and a city, the behavior of the system may change depending on the order in which the fields are set. For example, before a state is selected, the city list may show all possible cities (or no city), while after a state is selected the city list contains cities from the selected state. Despite its significance, current CTD technologies do not take into account the order in which values for the attributes are set.